package com.test.sort;

/**
 * 插入排序，最好时间复杂度为 O(n)，最坏时间复杂度为 O(n^2)
 */
public class InsertSortHandler implements ISortHandler{
    @Override
    public void handle(Integer[] arr) {
        int num = 0;
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int tmp = arr[i];
            int j = i;
            while ( j > 0 && arr[i] < arr[j - 1]) {
                num++;
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = tmp;
        }
        System.out.println("insert sort num:" + num);
    }
}
